<!DOCTYPE html>

<html>
<head>
    <meta charset="utf-8" />
    <title>TopCoder SRM 557 - 250: FoxAndMountainEasy</title>
    
    <link type="image/x-icon" rel="shortcut icon" href="http://www.topcoder.com/i/favicon.ico"/>
    

    
    <style type="text/css">
        /* font */
body {
    font-family: Helvetica, Arial, Verdana, sans-serif;
    font-size: 16px;
    line-height: 1.2em;
}
ul.constraints > li:before, ul.notes > li:before {
    font-family: monospace;
    font-weight: normal;
}
.heading {
    font-weight: bold;
    font-size: 175%;
    line-height: 1.2em;
}
.section .section-title {
    font-weight: bold;
    font-size: 125%;
}
ol.testcases > li:before {
    font-family: monospace;
}
type {
    font-weight: bold;
    font-family: monospace;
}
li.testcase .data {
    font-family: monospace;
    line-height: 1.5em;
}

/* layout */
.heading {
    margin-top: 0.1em;
    margin-bottom:0.1em;
    text-align: center;
}
.section .section-title {
    margin-top : 1em;
    margin-bottom: 1em;
}
.problem-intro, note, user-constraint {
    padding-left: 1.25em;
}

/* Lists */
ul.constraints, ul.notes, ul.variables, ul.problem-definition-lines {
    list-style-type: none;
    padding: 0px;
}
ul.constraints > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}
ul.notes > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}

/* Testcases */
li.testcase {
    line-height: 1.1em;
    padding-top: 0.625em;
    padding-bottom: 0.625em;
    overflow: auto;
}
li.testcase > .testcase-content > div { padding-bottom: 0.5em; padding-left: 1em; }

li.testcase .testcase-comment {
    margin: 0;
    padding-left: 1em;
}
.testcase-comment p:first-child { margin-top: 0; }
.testcase-comment p:last-child { margin-bottom: 0; }

li.testcase .testcase-content {
    margin: 0.31em;
}

/* Data and variables */
.testcase-output {
    padding: 0.2em 1em 0.2em 0em;
}
.variables, .testcase-output {
    margin-left: 0.5em;
    display: table;
    margin-bottom: 0px;
    margin-top: 0px;
}
.variable {
    display: table-row;
}
.variable .name {
    padding: 0.2em 0em 0.2em 1em;
    font-weight: bold;
    display: table-cell;
    text-align: right;
}
.testcase-output .prefix {
    padding: 0.2em 0em 0.2em 1em;
    display: table-cell;
}
.testcase-output .prefix:after {
    content : ":";
    padding-right: 0.5em;
}
.variable .name:after {
    font-weight: bold;
    content : ":";
    padding-right: 0.5em;
}
.variable .value, .testcase-output .value {
    padding: 0.2em 1em 0.2em 0em;
    display: table-cell;
}
ol.testcases {
    padding: 0px;
    counter-reset: test_number -1;
}
ol.testcases > li {
    list-style:none;
}
ol.testcases > li:before {
    counter-increment:test_number;
    display: block;
    clear: both;
    content:counter(test_number) ")";
    color: inherit;
    background: inherit;
}

/* Problem Definition */
.problem-definition, .problem-limits {
    padding-left: 1.25em;
}
.problem-definition-lines, .limit-lines {
    display: table;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-left: 0px;
}
.definition-line, .limit-line {
    display: table-row;
    height: 1.5em;
    overflow: auto;
}
.limit-name:after {
    content: ":";
    margin-right: 1em;
}
.definition-name, .definition-value, .limit-name, .limit-value {
    display: table-cell;
}
.definition-value {
    padding-left: 0.5em;
}
.definition-name:after {
    content: ":";
}
#contest-division:before {
    content: "Div ";
}
#problem-score:before {
    content: "- Problem ";
}
#problem-name {
    display: block;
}

/* Tags, hidden default */
.tag {
    visibility: hidden;
    position: absolute;
}

        body {
    /* font color */
    color: #333333;
    /* background color */
    background-color: white;
}
.section .section-title {
    /* title color */
    color: black;
}
li.testcase .data {
    /* highlight color */
    background: #eee;
}

    </style>
    
    
    

</head>

<body>
    <h1 class="heading">
        <span id='contest-name'>SRM 557</span>
        <span id='contest-division'>1</span>
        <span id='problem-score'>250</span>
        <span id='problem-name'>FoxAndMountainEasy</span>
    </h1>

    <hr />

    <!-- Problem Statement -->
    <div class="section">
        <h2 class="section-title">Problem Statement</h2>
        <div class="problem-intro">
            <intro escaped="1">Fox Ciel lives in a beautiful countryside.
She loves climbing mountains.
Yesterday, she went hiking in the mountains.
<br />
<br />
<br />
Her trip can be described as a sequence of (n+1) integers: h[0], h[1], ..., h[<b>n</b>]. 
These values represent altitudes visited by Fox Ciel during the trip, in order.
Fox Ciel does not remember the precise sequence, but she remembers the following:
<ul>
<li>for each i, h[i] &gt;= 0</li>
<li>h[0] = <b>h0</b></li>
<li>h[<b>n</b>] = <b>hn</b></li>
<li>for each i, abs(h[i+1]-h[i]) = 1</li>
</ul>
<br />
<br />
<br />
The last condition means that in each step the altitude of Fox Ciel either increased by 1, or decreased by 1.
We will call the two types of steps &quot;steps up&quot; and &quot;steps down&quot;, respectively.
Steps up will be denoted 'U' and steps down will be denoted 'D'.
<br />
<br />
<br />
You are given the <type>int</type>s <b>n</b>, <b>h0</b>, and <b>hn</b>: the length of the trip, the altitude at the beginning, and the altitude at the end.
In addition to these, Fox Ciel remembers some contiguous segment of her trip.
You are given this segment as a <type>String</type> <b>history</b>.
Each character of <b>history</b> is either 'U' or 'D'.
<br />
<br />
<br />
Check whether there is a valid trip that matches everything Fox Ciel remembers.
Return &quot;YES&quot; (quotes for clarity) if there is at least one such trip, or &quot;NO&quot; if there is none.</intro>
        </div>
    </div>
    
    <!-- Problem definition -->
    
    <div class="section" id="definition">
        <h2 class="section-title">Definition</h2>
        <div class="problem-definition">
            <ul class="problem-definition-lines">
                <li class="definition-line" id='class-line'>
                    <span class='definition-name'>Class</span>
                    <span class='definition-value'>FoxAndMountainEasy</span>
                </li>
                <li class="definition-line" id='method-line'>
                    <span class='definition-name'>Method</span>
                    <span class='definition-value'>possible</span>
                </li>
                <li class="definition-line" id='parameters-line'>
                    <span class='definition-name'>Parameters</span>
                    <span class='definition-value'>
                    
                        integer
                    , 
                        integer
                    , 
                        integer
                    , 
                        string
                    
                    </span>
                </li>
                <li class="definition-line" id='returns-line'>
                    <span class='definition-name'>Returns</span>
                    <span class='definition-value'>
                        string
                    </span>
                </li>
                <li class="definition-line" id='signature-line'>
                    <span class='definition-name'>Method signature</span>
                    <span class='definition-value'>
                        def possible(self, n, h0, hn, history)
                    </span>
                </li>
            </ul>
            <div class="problem-definition-public-tip">(be sure your method is public)</div>
        </div>        
    </div>
    

    <!-- Limits -->
    <div class="section">
        <h2 class="section-title">Limits</h2>
        <div class='problem-limits'>
            <ul class="limit-lines">
                <li class='limit-line'>
                    <span class='limit-name'>Time limit (s)</span>
                    <span class='limit-value'>2.000</span>
                </li>
                <li class='limit-line'>
                    <span class='limit-name'>Memory limit (MB)</span>
                    <span class='limit-value'>64</span>
                </li>
            </ul>
        </div>
    </div>

    
    
    <!-- Constraints -->
    <div class="section">
        <h2 class="section-title">Constraints</h2>
        <ul class="constraints">
        
            <li><user-constraint escaped="1"><b>n</b> will be between 1 and 100,000, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1"><b>history</b> will contain between 1 and min(50,<b>n</b>) characters, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1">Each character in <b>history</b> will be either 'U' or 'D'.</user-constraint></li>
        
            <li><user-constraint escaped="1"><b>h0</b> will be between 0 and 100,000, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1"><b>hn</b> will be between 0 and 100,000, inclusive.</user-constraint></li>
        
        </ul>
    </div>

    <!-- Test cases -->
    <div class="section">
        <h2 class="section-title">Test cases</h2>
        <ol class="testcases" start='0'>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">n</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">h0</span>
                                <span class="value data">
                                
                                    0
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">hn</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">history</span>
                                <span class="value data">
                                
                                    &quot;UU&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            &quot;YES&quot;
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment">The only solution is: h[] = {0, 1, 2, 3, 4}, the history of the entire trip will be &quot;UUUU&quot;.</div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">n</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">h0</span>
                                <span class="value data">
                                
                                    0
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">hn</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">history</span>
                                <span class="value data">
                                
                                    &quot;D&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            &quot;NO&quot;
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment">Based on <b>n</b>, <b>h0</b> and <b>hn</b>, the history of the entire trip must be &quot;UUUU&quot;. There is no 'D' in this history.</div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">n</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">h0</span>
                                <span class="value data">
                                
                                    100000
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">hn</span>
                                <span class="value data">
                                
                                    100000
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">history</span>
                                <span class="value data">
                                
                                    &quot;DDU&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            &quot;YES&quot;
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment">We have the following solution: h[] = {100000, 100001, 100000, 99999, 100000}, the history of the entire trip is &quot;UDDU&quot;.</div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">n</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">h0</span>
                                <span class="value data">
                                
                                    0
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">hn</span>
                                <span class="value data">
                                
                                    0
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">history</span>
                                <span class="value data">
                                
                                    &quot;DDU&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            &quot;NO&quot;
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">n</span>
                                <span class="value data">
                                
                                    20
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">h0</span>
                                <span class="value data">
                                
                                    20
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">hn</span>
                                <span class="value data">
                                
                                    20
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">history</span>
                                <span class="value data">
                                
                                    &quot;UDUDUDUDUD&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            &quot;YES&quot;
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">n</span>
                                <span class="value data">
                                
                                    20
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">h0</span>
                                <span class="value data">
                                
                                    0
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">hn</span>
                                <span class="value data">
                                
                                    0
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">history</span>
                                <span class="value data">
                                
                                    &quot;UUUUUUUUUU&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            &quot;YES&quot;
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">n</span>
                                <span class="value data">
                                
                                    20
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">h0</span>
                                <span class="value data">
                                
                                    0
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">hn</span>
                                <span class="value data">
                                
                                    0
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">history</span>
                                <span class="value data">
                                
                                    &quot;UUUUUUUUUUU&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            &quot;NO&quot;
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
        </ol>
    </div>
    <hr />

    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
</body>
</html>
